package com.jc.algorithmes.binarytree;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 二叉树的前中序遍历：
 * 1.先遍历根/做节点，再遍历第左右/根右节点，依次类推
 * 2.采用Morris实现
 */

public class MirrorsOrderDemo {

    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7,null,null);
        TreeNode node6 = new TreeNode(6,null,null);
        TreeNode node5 = new TreeNode(5,node6,node7);
        TreeNode node4 = new TreeNode(4,null,null);
        TreeNode node3 = new TreeNode(3,null,null);
        TreeNode node2 = new TreeNode(2,node4,node5);
        TreeNode node1 = new TreeNode(1,node2,node3);

        mirrorsPreOrder(node1);

    }

    public static void mirrorsPreOrder(TreeNode cur){
        if (cur == null){
            return;
        }
        TreeNode mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null){   //建立线索指针
                    mostRight.right = cur;
                    System.out.println(cur.val);//前序打印：打印根节点
                    cur = cur.left;
                    continue;
                }else { //mostRight.right = cur 删除线索指针
                    mostRight.right = null;
                }
            }else {
                System.out.println(cur.val);//前序打印：打印左边子节点
            }
            //中序遍历
//            System.out.println(cur.val);
            cur = cur.right;
        }
    }


    public static void mirrorsMidOrder(TreeNode cur){
        if (cur == null){
            return;
        }
        TreeNode mostRight = null;
        while (cur != null){
            mostRight = cur.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != cur){
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null){   //建立线索指针
                    mostRight.right = cur;
//                    System.out.println(cur.val);//前序打印：打印根节点
                    cur = cur.left;
                    continue;
                }else { //mostRight.right = cur 删除线索指针
                    mostRight.right = null;
                }
            }else {
//                System.out.println(cur.val);//前序打印：打印左边子节点
            }
            //中序遍历
            System.out.println(cur.val);
            cur = cur.right;
        }
    }

}
